import java.util.HashSet;

// 位图的实现
// Bitset(int size)
// void add(int num)
// void remove(int num)
// void reverse(int num)
// boolean contains(int num)
public class Bitset {
    //对数器测试
    public static void main(String[] args) {
        int n = 10000; //测试范围
        int testTime = 10000;  //测试次数
        bitset bt = new bitset();
        bt.Bitset(n);
        HashSet<Integer> set = new HashSet<>();  //用HashSet做测试
        System.out.println("测试开始");
        System.out.println("调用阶段开始");
        for(int i = 0; i < testTime; i++) {
            double decide= Math.random();  //获得一个[0-1)随机数
            int num = (int)(Math.random() * n) ;
            if(decide < 0.333) {  //随机进行一种操作
                bt.add(num);
                set.add(num);
            } else if(decide < 0.666) {
                bt.remove(num);
                set.remove(num);
            } else {
                bt.reverse(num);
                if(set.contains(num)) {
                    set.remove(num);
                }
                else {
                    set.add(num);
                }
            }
        }
        System.out.println("调用阶段结束");
        System.out.println("验证阶段开始");
        for(int i = 0; i < n; i++) {
            if(bt.contains(i) != set.contains(i)) {
                System.out.println("出错了");
            }
        }
        System.out.println("验证阶段结束");
        System.out.println("测试结束");
    }

    static class bitset {
        public int[] set;


        public void Bitset(int n) { //设置大小
            set = new int[(n+31)/32];
        }

        //添加
        public void add(int num) {
            // num/32表示num存储在数组的哪个下标
            // num%32表示num在32位比特位中的第几位
            set[num / 32] |= 1 << ( num % 32 );
        }

        //删除
        public void remove(int num) {
            set[num / 32] &= ~ (1 << ( num % 32) );  //将原本比特位存在的1变0, 0还是0,其余为不变
        }

        public void reverse(int num) {
            set[num / 32] ^= 1 << ( num % 32) ;    //将原本比特位存在的1变0, 0变1  （1^1=0, 0^1=1）
        }

        public boolean contains(int num) {
            return  ( set[num / 32] >>> ( num % 32)  & 1 ) == 1;
        }

    }

}
